#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int nthUglyNumber(int n)
    {
        if (n == 1) return 1;
        // else if(n == 2) return 2;
        // else if(n == 3) return 3;

        std::unordered_set<long long> visited = { 2,3,5 };
        std::queue<long long> q2;
        q2.push(2);
        std::queue<long long> q3;
        q2.push(3);
        std::queue<long long> q5;
        q5.push(5);

        int ans = 0;
        for (int i = 2; i <= n; ++i)
        {
            long long front2 = q2.empty() ? INT_MAX : q2.front();
            long long front3 = q3.empty() ? INT_MAX : q3.front();
            long long front5 = q5.empty() ? INT_MAX : q5.front();

            long long minNext = std::min(front2, std::min(front3, front5));
            // printf("minNext:%d\n", minNext);

            if (!q2.empty() && minNext == q2.front())
            {
                ans = q2.front();
                q2.pop();
            }
            else if (!q3.empty() && minNext == q3.front())
            {
                ans = q3.front();
                q3.pop();
            }
            else
            {
                ans = q5.front();
                q5.pop();
            }

            if (visited.count(2 * minNext) == 0)
            {
                visited.insert(2 * minNext);
                q2.push(2 * minNext);
            }

            if (visited.count(3 * minNext) == 0)
            {
                visited.insert(3 * minNext);
                q3.push(3 * minNext);
            }

            if (visited.count(5 * minNext) == 0)
            {
                visited.insert(5 * minNext);
                q5.push(5 * minNext);
            }
        }

        return ans;
    }
};